Journal
Scientific and Technical Journal of Information Technologies, Mechanics and Optics
UDK65.012.122
Issue:1 (159)
Download PDF0 Kbyte
Scheduling distributed computations in non-deterministic systems
Annotation
Computation scheduling is very important in the design of distributed information processing and control systems. Effective scheduling algorithms allow developer to find technical solutions that are adequate to the existing constraints. This is especially important for computers located on autonomous carriers, such as unmanned aerial vehicles, autonomous underwater vehicles, and other vehicles. Scheduling algorithms for tasks in the distributed non-deterministic computing system, when the task execution time is known inaccurately and described as time interval, are proposed and researched. The solution of the problem is achieved by reducing it to a known problem of flow shop scheduling with subsequent application of the formalism of solvable classes of distributed computing systems. Authors propose two algorithms for scheduling tasks for a non-deterministic distributed computing system. Algorithms allow the absence of isomorphisms between task graphs and the graph of interprocessor communications for the system, and the presence of many information outputs and branches between tasks. In these conditions, it is impossible to use known algorithms of flow shop scheduling. Proposed algorithms assume preliminary reduction of the considered system to the required form and base on the provisions of interval analysis and the concept of a solvable class of distributed computing systems. Optimality criterion for proposed algorithms is the criterion of minimum average time a task remains in the system. Additionally, the criterion of minimum of maximum deviation from directive terms is used. For the introduced solvable classes of systems, optimal scheduling algorithms of polynomial complexity are proposed. These algorithms allow us to schedule computations in real distributed computing systems when the system deviates from the canonical form and when the durations of the tasks are not precisely known. Proposed algorithms can be applied when scheduling computations in real distributed computing systems and solving tasks with not precisely known durations and also, for example, in scheduling economic processes.
Keywords
Постоянный URL
Articles in current issue
- Multispectral optoelectronic system
- Study of the influence of laser wavelength on the dichroism effect in ZnO:Ag films
- Direct laser thermochemical writing on titanium films for rasterized images creation
- Algorithms of direct output-feedback adaptive control of a linear system with finite time tuning
- Large language models in information security and penetration testing: a systematic review of application possibilities
- Usage of polar codes for fixed and random length error bursts correction
- Efficient sparse retrieval through embedding-based inverted index construction
- Method of semantic segmentation of airborne laser scanning data of water protection zones
- Directional variance-based algorithm for digital image smoothing
- DAS signal modeling using the generative adversarial neural network technique
- Multidimensional trajectory planning algorithm for a 5D printer slicer
- Enhancing and extending CatBoost for accurate detection and classification of DoS and DDoS attack subtypes in network traffic
- Detection of L0-optimized attacks via anomaly scores distribution analysis
- Numerical study of SiO2 particle erosion of an aluminum alloy
- An approach to solving the problem of geomagnetic data scarcity in decision-making support
- Construction of matched distance function for simple Markov channel
- Application of the dynamic regressor extension and mixing approach in machine learning on the example of perceptron
- WaveVRF: post-quantum verifiable random function based on error-correcting codes